\documentclass{amsart}

\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[ngerman]{babel}
\usepackage{parskip}
\usepackage[colorlinks=true]{hyperref}
\usepackage{amsmath,amssymb,amsthm}

% Auskommentieren für eine Version mit normalen Zeilenabstand
\linespread{1.8}

\theoremstyle{definition}
\newtheorem{Def}{Definition}[section]
\newtheorem{Bsp}[Def]{Beispiel}
\theoremstyle{plain}
\newtheorem{Lemma}[Def]{Lemma}
\newtheorem{Satz}[Def]{Satz}

% := und =:
\newcommand*{\defeq}{\mathrel{\vcenter{\baselineskip0.5ex \lineskiplimit0pt\hbox{\scriptsize.}\hbox{\scriptsize.}}}=}
\newcommand*{\eqdef}{=\mathrel{\vcenter{\baselineskip0.5ex \lineskiplimit0pt \hbox{\scriptsize.}\hbox{\scriptsize.}}}}

\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\rang}{d}
\DeclareMathOperator{\Sym}{\mathsf{Sym}}


\title{Anzahlen endlicher Gruppen I:\\Einführung ins Thema}
\author[J.\,M. Petschick]{Jan Moritz Petschick} 

\begin{document}

\maketitle

\section{Die Fragestellung und ihre Formulierung}
\label{sec:die_fragestellung_und_ihre_formulierung}

Dieses Seminar beschäftigt sich mit folgender Fragestellung:

\begin{center}
	Wieviele Gruppen der Ordnung $n \in \N$ gibt es?
\end{center}

Liest man dies wörtlich erhält man keine sinnvolle Antwort, denn natürlich kann man durch Umbennung der Elemente einer einzigen Gruppe beliebig viele neue Gruppen erhalten. Jede Menge derselben Kardinalität stellte eine Gruppe dar, und die folgerichtige Antwort auf die Frage wäre: „Die Klasse aller Gruppen der Ordnung $n$ ist unabhängig von $n$ eine echte Klasse (und damit keine Menge).“

Diese Antwort ist nicht jene, die wir suchen. Daher schränken wir uns weiter ein und fragen:

\begin{center}
	Wieviele Isomorphieklassen von Gruppen der Ordnung $n \in \N$ gibt es?
\end{center}

Die Antwort auf diese Frage kann man nun in einer Funktion darstellen. Als generelle Konvention nennen wir diese

\begin{align*}
	f: \N &\to \N \\
	n &\mapsto \# \text{ Menge aller Isomorphieklassen von Gruppen der Ordnung } n.
\end{align*}

Andere solche \emph{Zählfunktionen} werden wir ähnlich benennen und eventuell mit Subskripten ausstatten.

Zurück zu unserer Frage. Ein sinnvoller erster Versuch zu einer Antwort wäre es, die ersten Werte von $f$ zu berechnen. Für kleine Zahlen sind diese Werte schon lange bekannt, und mit Hilfe grundlegender Sätze und Methoden kann man sie selbst nachrechnen. Bis $n = 16$ sind die Werte in Tabelle \ref{tab:Kleine_Werte} wiedergegeben.

\begin{table}[ht]
	\centering
	\begin{tabular}{c|*{16}{c}}
		$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\
		\hline
		$f(n)$ & 1 &  1 &  1 &  2 &  1 &  2 &  1 &  5 &  2 &  2 &  1 &  5 &  1 &  2 &  1 &  14 
	\end{tabular}
	\caption{$f(n)$ für kleine Werte von $n$.}
	\label{tab:Kleine_Werte}
\end{table}

Wer mehr sehen möchte, kann sich \href{https://oeis.org/A000001}{diese (die erste!) Folge} der \emph{The On-Line Encyclopedia of Integer Sequences} ansehen. Noch mehr findet man in der Arbeit von Besche, Eick und O’Brien, wobei wir  vor allen an den beiden folgenden Resultaten daraus interessiert sind:

\begin{align*}
	f(2^{10}) = f(1024) &= 49 487 365 422\\
	\sum_{n = 1}^{2000} f(n) &= 49 910 529 484
\end{align*}

Das heißt, dass $\frac{49 487 365 422}{49 910 529 484} \approx 99,15 \%$ aller (Isomorphieklassen von) Gruppen der Ordnung $\leq 2000$ von Ordnung $2^{10}$ sind! Schaut man sich die obige Tabelle noch einmal an, stellt man ein ganz ähnliches Verhalten im kleinen fest. Es sind $14$ von $42$, also immerhin ein Drittel, der Gruppen von Ordnung $\leq 16$ genau von Ordnung $16$.

Auf der anderen Seite kennen wir den Satz, dass alle Gruppen von Primzahlordnung zyklisch sind, das heißt, dass für alle Primzahlen $p$ gerade $f(p) = 1$ gilt. (Andersherum gilt das nicht: Obwohl $15$ nicht prim ist, gilt $f(15) = 1$.) Damit drängt sich folgende Vermutung auf: Der Wert $f(n)$ is groß, wenn $n$ viele Teiler hat, und klein, wenn $n$ wenige Teiler hat. Konkreter wollen wir folgende Maße für die \emph{arithmetische Größe} einer natürlichen Zahl definieren:

\begin{Def}
	Sei $n \in \N$ eine positive ganze Zahl mit Primfaktorzerlegung
	\[
		n = \prod_{i = 1}^\ell p_i^{\alpha_i},
	\]
	dass heißt $p_i$ ist prim und $\alpha_i \in \N$ für $i = 1, \dots, \ell$, und $p_i = p_j$ impliziert $i = j$. Wir definieren
	\begin{align*}
		\mu(n) &\defeq \max_{i = 1}^{\ell} \alpha_i\\
		\lambda(n) &\defeq \sum_{i = 1}^{\ell} \alpha.
	\end{align*}
\end{Def}

Achtung! Die Funktion $\mu$ ist \emph{nicht} die häufig in der Zahlentheorie verwendete \emph{Möbius-Funktion}, die oft ebenfalls mit $\mu$ bezeichnet wird.

Außerdem erkennen wir, dass unmöglich scheint eine exakte Formel für $f(n)$ anzugeben. Was wir suchen ist also eine \emph{Abschätzung} für den Wert von $f$ abhängig von $n$. Um auch dieses zu präzisieren definieren wir:

\begin{Def}
	Seien $k, l: \N \to \R$ zwei Funktionen. Wir schreiben
	\[
		k(n) \leq \mathcal O(l(n))
	\]
	(und analog $\leq, =$) falls eine positive Zahl $M \in \R_+$ existiert, sodass ein $n_0 \in \N$ exisiert, ab welchem für alle $n > n_0 \in N$ die folgende Abschätzung gilt:
	\[
		k(n) \leq Ml(n).
	\]
	Diese Konvention nennt man \emph{Landau-$\mathcal{O}$}-Notation.
\end{Def}

\begin{Bsp}
	\leavevmode % Nötig, falls ein Satz/Lemma/... mit einer Liste anfängt
	\begin{enumerate}
		\item Einige Klassen von Funktionen lassen sich durch das Landau-$\mathcal O$ einfach beschreiben. Zum Beispiel sind die beschränkten Funktionen gerade die Funktionen $k$, für welche $k \leq \mathcal O(1)$ gilt. Dabei beschreibt $1$ die konstante Funktion.
		\item Von großem Interesse ist es, wie sich Zählfunktionen in die Hierarchie von polynomiellen, also $\mathcal O(P)$ mit einem Polynom $P$, und exponentiellen, also $\mathcal O(\exp)$, einordnen.
	\end{enumerate}
\end{Bsp}

\section{Resultate}
\label{sec:resultate}

Im Verlaufe des Seminars werden wir die Beweise für die beiden folgenden Resultate über die approximative von $f$ untersuchen. Dabei gelten diese zunächst nur für Primzahlpotenzen, was aber im Angesicht der im vorherigen Abschnitt erklärten Vermutung ein plausibler Startpunkt ist.

\begin{Satz}
	Sei $p$ eine Primzahl. Dann gilt für natürliche Zahlen $m \in \N$
	\begin{align*}
		f(p^m) \geq p^{\frac 2 {27} m^3 - \mathcal O(m^2)}.
	\end{align*}
\end{Satz}

\begin{Satz}
	Sei $p$ eine Primzahl. Dann gilt für natürliche Zahlen $m \in \N$
	\begin{align*}
		f(p^m) \leq p^{\frac 2 {27} m^3 + \mathcal O(m^{\frac 8 3})}.
	\end{align*}
\end{Satz}

Tatsächlich liegen wir damit schon in einem engen Wachstumsfenster. Beachtet man, dass $\mu(p^m) = m = \lambda(p^m)$ gilt, stellt sich die Frage danach, welches arithmetische Größenmaß die Potenz verallgemeinert.

In der zweiten Hälfte des Seminars beschäftigen wir uns mit einem Spezialfall des Satzes von Pyber, dessen allgemeine Form eine sehr präzise Antwort auf unsere zentrale Frage liefert:

\begin{Satz}
	Es gilt:
	\begin{align*}
		f(n) \leq n^{\frac 2 {27} \mu(n)^3 + \mathcal O(\mu(n)^{\frac 5 3})}.
	\end{align*}
\end{Satz}

\section{Elementare Abschätzungen}
\label{sec:elementare_abschatzungen}

\begin{Def}[Hierachie von gruppenähnlichen algebraischen Strukturen]
	\leavevmode
	\begin{enumerate}
		\item Eine nicht-leere Menge $M$ mit einer Operation
		\[
			\cdot: M \times M \to M
		\]
		heißt \emph{Magma}.
		\item Ein Magma $M$ mit einem Element $1_M$ mit der Eigenschaft
	\[
		1_M \cdot m = m = m \cdot 1_M
	\]
	für alle $m \in M$ heißt \emph{unitäres Magma}. Das Element $1_M$ heißt neutrales Element.
		\item Ein Magma, in dem das Assoziativgesetz gilt, heißt \emph{Halbgruppe}.
		\item Ein Magma $M$ mit der Eigenschaft, daß für alle $m, n \in M$ Elemente $x, y \in M$ existieren, sodaß
		\[
			m \cdot x = n \text{ und } y \cdot m = n
		\]
		gelten, heißt \emph{Quasigruppe}.
	\end{enumerate}
\end{Def}

Jedes endliche Magma wird vollständig durch seine Multiplikationstafel (auch \emph{Cayley-Tafel} genannt) beschrieben, also durch die Matrix $(m \cdot n)_{m,n \in M} \in M^{|M|^2}$. Dadurch läßt sich die Anzahl der möglichen Magmas einer bestimmten Größe einfach abschätzen. Es gilt:
\[
	f_{\mathrm{Magma}}(n) \leq n^{n^2}.
\]
Da Magmas keine algebraischen Eigenschaften (wie Assoziativität, Kommutativität, \&c.) erfüllen müssen, definieren wir den \emph{Isomorphimsus von Magmas} als Bijektion der unterliegenden Mengen. Natürlich soll $f_{\mathrm{Magma}}$ die Zahl der Magmas bis auf Isomorphie beschreiben. Also wissen wir, daß eine untere Schranke für $f_{\mathrm{Magma}}$ durch
\[
	\frac{n^{n^2}}{n!}
\]
gegeben wird.

Wie zu erwarten bringt uns diese Abschätzung noch kaum einen Schritt an die Resultate für Gruppen heran. Auch der Übergang zu unitären Magmas ist nicht bedeutsam, da bei diesen lediglich eine Spalte und Zeile in der Cayley-Tafel festgelegt ist (die des neutralen Elementes), d.h.
\[
	\frac{n^{{n-1}^2}}{(n-1)!} \leq f_{\mathrm{uni. Magma}}(n) \leq n^{{n-1}^2}.
\]
Größere Hoffnung einer Annäherung an die Ergebnisse für Gruppen liegt im Übergang zu Halb- oder Quasigruppen.

\begin{Satz}
	Sei $\epsilon > 0$. Dann existiert ein $n_0 \in \N$, sodaß für alle $n > n_0$ folgendes gilt:
	\[
		f_{\mathrm{Halbgruppen}}(n) \geq n^{(1-\epsilon)n^2}.
	\]
\end{Satz}

\begin{proof}
	Die Idee ist es, strukturell sehr einfach zu beschreibenden Halbgruppen zu konstruieren. Sei $M \neq \emptyset$ eine durch $<$ linear geordnete Menge, d.h. bis auf Umbenennung $\{0, \dots, |M|-1\}$ mit der natürlichen Ordnung. Wähle $m \in M$ beliebig und definiere
	\[
		i \cdot j = \begin{cases}
			0, &\text{ falls } i < m \text{ oder } j < m\\
			\text{beliebig in } \{ n \in M \mid n < m\} &\text{ andernfalls.}
		\end{cases}
	\]
	Unabhängig von der konkreten Wahl im zweiten Fall erhalten wir eine Halbgruppe: Es gilt für alle $i, j, k \in M$
	\[
		\underbrace{(i \cdot j)}_{< m} \cdot k = 0 = i \cdot \underbrace{(j \cdot k)}_{< m}.
	\]
	Es gilt also für jedes $m \in M$
	\[
		f_{\mathrm{Halbgruppen}}(n) \geq \frac{m^{(n-m)^2}}{n!}.
	\]
	Wählt man $m \defeq n^{(1-\frac 1 2 \epsilon)}$ ergibt sich
	\[
		f_{\mathrm{Halbgruppen}}(n) \geq n^{(1-\frac 1 2 \epsilon)(n-n^{1 - \frac 1 2 \epsilon})}.
	\]
	Für große $n \in N$ gilt damit $f_{\mathrm{Halbgruppen}}(n) \geq n^{(1-\epsilon)n^2}$.
\end{proof}

Trotz Assoziativität bleiben wir also sehr dicht an $n^{n^2}$. Die nächste Hoffnung sind die Quasi-Gruppen. Um diese besser zu verstehen betrachten wir folgendes Lemma:

\begin{Lemma}
	Ein Magma $M$ ist genau dann eine Quasigruppe, wenn seine Multiplikationstafel ein \emph{lateinisches Quadrat} ist, d.h. wenn in jeder Zalte und Speile jedes Element von $M$ genau einmal vorkommt.
\end{Lemma}

\begin{proof}
	Angenommen $M$ ist eine Quasigruppe. In der Spalte von $m \in M$ taucht $n \in M$ auf, denn es existiert $x \in M$ mit $m \cdot x = n$. Analoges gilt für die Zeilen der Tafel, mit der Existenz von $y \in M$, sodaß $y \cdot m = n$. Die Rückrichtung ist klar.
\end{proof}

Leider ist die Zahl der Lateinischen Quadrate einer fixen Größe ein Mysterium; es ist keine Asymptotik bekannt. Aber ein Satz von M. Hall besagt:
\[
	n^{\frac 1 2 n^2 - \mathcal O(n)} \leq f_{\mathrm{Lateinische\;Quadrate}}(n) \leq n^{n^2}.
\]
Also reicht auch die Invertierbarkeit nicht für eine signifikante Reduktion der Anzahl der Objekte aus. Man muß also tatsächlich alle drei Eigenschaften der Gruppe – Assoziativität, Invertierbarkeit und Unitarität – gleichzeitig betrachten.

\begin{Satz}[Elementare obere Schranke]
	Es gilt
	\[
		f(n) \leq n^{n\lambda(n)}.
	\]
\end{Satz}

\begin{proof}
	Definiere den Rang von $G$ durch
	\[
		\rang(G) \defeq \min\{ |X| \mid X \subseteq G, \langle X \rangle = G\},
	\]
	also als die minimale Größe eines Erzeugendensystems von $G$. Dann gilt 
	\[
		\lambda(|G|) \geq \rang(G).
	\]
	Dies wird wie folgt bewiesen: Sei
	\[
		G = G_r > G_{r-1} > \dots > G_1 > G_0 = \{ 1 \}
	\]
	eine maximale Kette ineinander enthaltener Untergruppen von $G$. Wähle für jedes $i \in \{ 1, \dots, r \}$ ein Element $g_i \in G_i \setminus G_{i-1}$. Dann gilt $\langle g_i \mid i \in \{ 1, \dots, j \} \rangle = G_{j}$, denn wäre $\langle g_i \mid i \in \{ 1, \dots, j \} \rangle < G_{j}$ könnte man die Kette verfeinern. Damit ist $r > \rang(G)$.
	Nach dem Satz von Lagrange gilt
	\[
		|G| = \prod_{i = 1}^r |G_i : G_{i-1}|.
	\]
	Damit ist nun $r \leq \lambda(|G|)$, denn $\lambda(|G|)$ ist die maximale Länge eines Produktes von Zahlen aus $\N_{> 1}$, welches $|G|$ ergibt. Dies beweist die Behauptung $\lambda(|G|) \geq \rang(G)$.
	
	Nach dem Satz von Cayley gilt bis auf Isomorphie $G \leq \Sym(|G|)$. Also
	\begin{align*}
		f(n) &\leq \# \text{Untergruppen der Ordnung $n$ von } \Sym(n)\\
		&\leq \# \lambda(n)\text{-erzeugte Untergruppen der Ordnung $n$ von } \Sym(n),
	\end{align*}
	nach obiger Behauptung, und konsequenterweise
	\begin{align*}
		f(n) &\leq \# \lambda(n)\text{-elementige Teilmengen von } \Sym(n)\\
		&= (n!)^{\lambda(n)}\\
		&\leq n^{n\lambda(n)}.
	\end{align*}
\end{proof}

\end{document}